

#include <stdio.h>
#include <stdbool.h>



int search_binary_first(int ** matrix,int rowSize,int target)
{



    int low = 0;
    int high = rowSize -1;

    while (low < high)
    {
        //matrix[mid][0] <= target 时，单纯的二分会使得low < high时,high-low = 1,mid不变,这里操作是为了使得在这种情况下，mid至少移动1个步长,
        int mid = (high - low + 1)/2 + low;

        if (matrix[mid][0] <= target)
        {
            low = mid;
        }
        else
        {
            high = mid -1;
        }
    }

    return low;
    

}

bool search_binary(int *matrix, int colSize,int target,int *colValue)
{

    int low = 0;
    int high = colSize - 1;

    while(low <= high)
    {
        int mid = (low + high )/2;

        if (matrix[mid] == target)
        {
            *colValue = mid;
            return true;
        }
        else if (matrix[mid] > target)
        {
            high = mid - 1;
        }
        else
        {
            low = mid +1;
        }
    }

    return false;
}



bool search_binary_2matrix(int **matrix, int rowSize,int colSize,int target)
{
    int rowIdx = search_binary_first(matrix,rowSize,target);
    int colIdx = -1;

    bool ret = search_binary(matrix[rowIdx],colSize,target,&colIdx);

    if (ret)
    {
        printf("\nTarget is exist and at Matrix[%d][%d]!\n\n",rowIdx,colIdx);
    }
    else
    {
        printf("\nTarget is not exist!\n\n");
    }

}

bool search_binary_2matrix_1(int **matrix,int rowSize,int colSize,int target)
{

    int low = 0;
    int high = rowSize * colSize -1;

    while (low <= high)
    {

        int mid = (low + high)/2;

        if (matrix[mid / colSize][mid % colSize] == target)
        {
            printf("\nTarget is at Matrix[%d][%d]!\n\n",mid / colSize,mid % colSize);
            return true;
        }
        else if (matrix[mid / colSize][mid % colSize] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    printf("\nTarget is not exist!\n\n");

    return false;
}




int main(int argc, char *argv[])
{





    int array[3][4] = { {1,2,3,4},
                        {5,6,7,8},
                        {9,10,11,12}};

    int *p[3] = {array[0],array[1],array[2]};//里面存储32位地址

    int **matrix = p;

    printf("test: %p %d %p \n",p[0],p[0][2],&p[0][2]);

    printf("test array: %p %p %p \n",array,array+1,array[2]);


    bool ret = search_binary_2matrix_1(matrix,3,4,14);

    return 0;
}